In a processor, SOC, and the like used for information processing, an on-chip or off-chip SRAM or SDRAM, a hard disk apparatus, or a storage device such as a flash memory, are used to apply predetermined processing to data.
As the information processing speeds up, the storage capacity required for processing increases, and the cost for semiconductor memories, such as on-chip or off-chip SRAM or SDRAM, also increases. It is also difficult to accommodate a memory with desired capacity within a certain size of package. Therefore, a data compression technique for reducing the size of redundant data to be processed and a data decompression technique for decompressing compressed data are essential in an information processing apparatus that requires high efficiency and high cost-effectiveness.
An LZ method (slide dictionary method) is conventionally known in a typical data compression/decompression process. In the LZ method, a dictionary is searched to check whether compression target data has appeared before. If the compression target data has appeared before, the data is replaced by information indicating an entry number of a storage location in the dictionary and a match length with registered data. If the compression target data has not appeared before, the data is registered in the dictionary as mismatch data and outputted without change.
The dictionary used in the LZ method is called a slide dictionary because new data replaces old data to update the dictionary. The LZ method is also called a dictionary-based compression method because a dictionary is used for compression and is capable of efficient lossless compression utilizing reappearance of data. Therefore, the LZ method is widely used in the field of data compression. FIG. 1 illustrates a processing procedure of the dictionary-based compression method.
FIG. 1 is a flow chart showing a processing procedure of a dictionary-based compression method.
As shown in FIG. 1, in the dictionary-based compression method, compression target input data is first fetched in step 41, and a search is made to determine whether the same data as the input data exists in the dictionary is searched in step 42.
If the same data as the input data exists in the dictionary, the process moves to step 43. An input number provided to the input data is replaced by a number indicating the storage location of the same data in the dictionary (dictionary entry number), and the dictionary entry number and a hit identifier indicative of the existence of the same data in the dictionary are outputted. Here, if the number of bits required to express the dictionary entry number is smaller than the size of the input data, the compression process is carried out.
If the same data as the input data does not exist in the dictionary, the process moves to step 44 to register the input data in the dictionary. In step 45, a hit-miss identifier indicating that the same data does not exist in the dictionary is added to the input data and outputted.
To decompress the data, the dictionary is restored from the data provided with the hit-miss identifier, and the compressed data (dictionary entry number) provided with the hit identifier is replaced by corresponding data in the dictionary to reproduce the original data.
Meanwhile, a compression method called RLE (Run Length Encoding) is used for transmitting data using a facsimile device and the like. The RLE is a method for compressing data to be processed by replacing the data with information indicating the number of repetitions of the same data pattern. FIG. 2 illustrates a processing procedure of the compression method by RLE.
FIG. 2 is a flow chart showing a processing procedure of a compression method by RLE.
As shown in FIG. 2, in RLE, compression target input data is first fetched in step 61, and whether the input data is the same as the previous data is determined in step 62. If the input data is the same as the previous data, the process moves to step 63, and “1” is added to a value of a preset iteration counter.
Next, in step 64, whether the value of the iteration counter has reached a preset specified value is determined. If the value has reached the specified value, a hit identifier indicating that the input data is the same as the previous data and the value of the iteration counter are outputted in step 65, and the value of the iteration counter is returned to “0” in step 66.
If the value of the iteration counter has not reached the specified value in step S64, the process returns to step 61. The next input data is fetched, and the processes from step 62 are repeated.
If the input data is determined not the same as the previous data in step 62, whether the value of the iteration counter is “0” is checked in step 67. If the value of the iteration counter is not “0”, the iteration count of the last time needs to be outputted. Therefore, a hit identifier and the value of the iteration counter are outputted in step 68, and the value of the iteration counter is returned to “0” in step 69. If the value of the iteration counter is 0, a hit-miss identifier indicating that the input data is not the same as the previous data and the input data are outputted without change in step 70. The input data is held as the previous data in step 71, and the process returns to step 61.
In this way, in the compression method by RLE, simple repetition characteristics included in a data string are used to compress data. Therefore, the compression method is effective for compressing image data and the like, but is not effective for normal calculation data and the like because the compression efficiency is not high enough. Therefore, it is preferable to use RLE by limiting the types of compression target data.
Consequently, a compression method with a combination of the LZ method and RLE is proposed in, for example, National Publication of International Patent Application No. 2003-521189 (hereinafter, called Patent Document 1) and Japanese Patent No. 3653226 (hereinafter, called Patent Document 2).
In Patent Document 1, a configuration is proposed in which an RLE coder that executes a compression process by the RLE is arranged at the latter part of a main coder that executes a dictionary-based compression process.
In Patent Document 1, information indicative of an RLE process is stored in a data storage area of the dictionary as shown in FIG. 3, and an entry number indicative of the area is used as a control code of the compression process by RLE. In the technique described in Patent Document 1, there is a problem in which the RLE coder needs to be always operated, and the RLE coder occupies part of the entries (data storage area with address 3 in FIG. 3) in the dictionary.
Meanwhile, Patent Document 2 describes a configuration for compressing data by the LZ method after compression of data by RLE. Patent Document 2 points out the low compression efficiency and the high processing cost of RLE and proposes a new compression method using RLE.
However, in a method with a combination of the dictionary-based compression method and another compression method (RLE or the like), processing circuits (such as logic circuit and CPU) that execute the compression process are always operated even if the compression method of the latter (RLE or the like) is not effective for the compression target data. Therefore, there is a problem in which power is unnecessarily consumed.
Furthermore, in a method that combines the dictionary-based compression method and the compression method of RLE, the RLE coder occupies part of the entries of the dictionary as described above. This causes a decrease in data compression efficiency. Particularly, compression efficiency decreases if the RLE compression method is not effective for the compression target data.